import BinarySearchTree from "./BinarySearchTree";
import TreeNode from "./treeNode";
import {Compare, compareType, defaultCompare} from "../utils/Compare";

/**
 * 平衡因子枚举
 */
enum BalanceFactorEnum {
  UNBALANCED_RiGHT,   // 做 RL 操作
  SLIGHTLY_UNBALANCED_RiGHT, // 做RR操作
  BALANCED,// 不做操作
  UNBALANCED_LEFT, // 做LL操作
  SLIGHTLY_UNBALANCED_LEFT, // 做LR操作
}

export default class AVLTree<T> extends BinarySearchTree<T> {
  constructor(compareFn: compareType<T> = defaultCompare) {
    super(compareFn);
  }

  /**
   * 计算树节点的高度
   * @param node 所需要计算的节点数
   */
  protected getNodeHeight(node: TreeNode<T> | null): number {
    if (node == null) {
      return -1;
    }

    return Math.max(
      this.getNodeHeight(<TreeNode<T>>node.left), this.getNodeHeight(<TreeNode<T>>node.right)
    ) + 1;
  }

  /**
   * 计算树的平衡因子
   * @param node
   */
  protected getBalanceFactor(node: TreeNode<T>): BalanceFactorEnum {
    const heightDiff = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDiff) {
      case -2:
        return BalanceFactorEnum.UNBALANCED_RiGHT;
      case -1:
        return BalanceFactorEnum.SLIGHTLY_UNBALANCED_RiGHT;
      case 1:
        return BalanceFactorEnum.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactorEnum.UNBALANCED_RiGHT;
      default:
        return BalanceFactorEnum.BALANCED;
    }
  }

  /*
  ===============================================================
  ==== ps:  下方出现的树的节点图中 -> 或 <- 指向的数字为平衡因子的值  =====
  ===============================================================

  需要注意的是 当  -1 <= 平衡因子 <= 1 时 不需要做操作

  树的旋转总共有四种
  1. LL (左-左) : 向右单旋转
  2. RR (右-右) : 向左单旋转
  3. LR (左-右) : 向右的双旋转(先执行LL旋转, 在执行RR旋转)
  4. RL (右-左) : 向左的双旋转(先执行RR旋转, 在执行LL旋转)

  LL旋转:
    出现的时机为节点左侧子节点高度大于右侧子节点高度时, 并且左侧节点也是平衡或左侧较重 如下
                          3 -> 2
                         /
                        2 -> 1
                       /
                      1 -> 0
    进行如下的旋转
                        2 -> 0
                       / \
                 0 <- 1   3 -> 0

  RR旋转:
    与LL旋转出现的时机恰恰相反, 它出现于右侧节点的高度大于左侧节点,并且右侧节点也是平衡或者右侧较重的  如下
                          1 -> -2
                           \
                            2 -> -1
                             \
                              3 -> 0
    进行如下旋转
                          2 -> 0
                         / \
                   0 <- 1   3 -> 0

  LR旋转:
    出现于左侧子节点的高度大于右侧子节点的高度, 并且左侧子节点右侧较重, 这时候可以先进行RR(左旋转)修复为 LL(左-左)的情况 然后进行LL(右旋转)修复 如下
                                3 -> 2
                               / \
                         1 <- 1  c4 -> 0
                             / \
                       0 <- c1  2 -> 0
                               / \
                         0 <- c2 c3 -> 0
    第一次旋转为如下
                                3 -> 2
                               / \
                         1 <- 2  c4 -> 0
                             / \
                       0 <- 1  c3 -> 0
                           / \
                     0 <- c1 c2 -> 0
    第二次旋转如下
                                 2    -> 0
                               /   \
                         0 <- 1     3  -> 0
                             / \   / \
                            c1 c2 c3 c4
                             |  |  |  |
                             0  0  0  0


  RL旋转
    与LR旋转情况刚好相反
    出现于右侧子节点的高度大于左侧子节点的高度, 并且右侧子节点左侧较重, 这时候可以先进行LL(右旋转)修复为 RR(右-右)的情况 然后进行RR(左旋转)修复 如下
                                1(-2)
                               /  \
                            c1(0)  3(1)
                                  /  \
                               2(0)   c4(0)
                               /  \
                             c2(0) c3(0)
    第一次旋转为如下
                                1(-2)
                               /  \
                            c1(0)  2(-1)
                                  /  \
                               c2(0)  3(0)
                                     /  \
                                  c3(0) c4(0)
    第二次旋转如下
                                 2    -> 0
                               /   \
                         0 <- 1     3  -> 0
                             / \   / \
                            c1 c2 c3 c4
                             |  |  |  |
                             0  0  0  0

   */

  /**
   * 进行LL变换 也就是向右单旋转
   * @param node
   */
  rotationLL(node: TreeNode<T>): TreeNode<T> {
    const tmp = <TreeNode<T>>node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  }

  /**
   * 进行RR变换 也就是向左单旋转
   * @param node
   */
  rotationRR(node: TreeNode<T>): TreeNode<T> {
    const tmp = <TreeNode<T>>node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
  }

  /**
   * LR变换  先执行LL(右旋) 在执行RR(左旋)
   * 左侧节点高度大于右侧节点, 左侧节点的右侧较重
   */
  rotationLR(node: TreeNode<T>): TreeNode<T> {
    node.left = this.rotationLL(<TreeNode<T>>node.left);
    return this.rotationRR(node);
  }

  /**
   * LR变换  先执行RR(右旋) LL(左旋)
   * 右侧节点高度大于左侧节点, 并且右侧节点的左侧较重
   */
  rotationRL(node: TreeNode<T>): TreeNode<T> {
    node.left = this.rotationRR(<TreeNode<T>>node.right);
    return this.rotationLL(node);
  }

  insert(key: T) {
    if (this.root == null) {
      this.root = new TreeNode<T>(key);
    } else {
      this.root = this.insertNode(this.root, key);
    }
  }

  protected insertNode(node: TreeNode<T>, key: T): TreeNode<T> {
    if (this.compareFn(node.key, key) === Compare.NORMAL_THAN) {
      return node
    }
    let index: "left" | "right";
    // 如果当前key 比 要插入的key小  则说明 插入key需要插入到 right
    if (this.compareFn(node.key, key) === Compare.LESS_THAN) {
      index = "right";
    } else {
      index = "left";
    }

    if (node[index] == null) {
      node[index] = new TreeNode(key);
    } else {
      this.insertNode(node[index] as TreeNode<T>, key);
    }

    // 做平衡操作
    const balanceFactor = this.getBalanceFactor(node);

    // 当前为左侧层级较深
    if (balanceFactor === BalanceFactorEnum.UNBALANCED_LEFT){
      // 如果当前node.left.key > key  说明key插入到了左侧  也就是下方的情况 需要进行LL(右旋)操作
      /*
            node
            /
          left
          /
        key
       */
      if(this.compareFn(key,(<TreeNode<T>>node.left).key) === Compare.LESS_THAN){
        node = this.rotationLL(node);
      }else{
        // 反之 进行LR操作
        /*
            node
            /
          left
             \
             key
       */
        node = this.rotationLR(node);
      }
    }


    // 当前为左侧层级较深
    if (balanceFactor === BalanceFactorEnum.UNBALANCED_RiGHT){
      // 如果当前node.right.key < key  说明key插入到了右侧  也就是下方的情况 需要进行RR(左旋)操作
      /*
            node
               \
              right
                 \
                  key
       */
      if(this.compareFn(key,(<TreeNode<T>>node.right).key) === Compare.LESS_THAN){
        node = this.rotationRR(node);
      }else{
        // 反之 进行RL操作
        /*
            node
                \
                right
                 /
              key
       */
        node = this.rotationRL(node);
      }
    }


    return node;
  }

  protected removeNode(node: TreeNode<T> | null, key: T): TreeNode<T> | null {
    super.removeNode(node, key);
    if(node == null){
      return null;
    }

    const balanceFactor = this.getBalanceFactor(node);
    if(balanceFactor === BalanceFactorEnum.UNBALANCED_LEFT){
      const balanceFactorLeft = this.getBalanceFactor(<TreeNode<T>>node.left)
      if(balanceFactorLeft === BalanceFactorEnum.BALANCED || balanceFactorLeft === BalanceFactorEnum.SLIGHTLY_UNBALANCED_LEFT){
        return this.rotationLL(node);
      }
      if (balanceFactorLeft === BalanceFactorEnum.SLIGHTLY_UNBALANCED_RiGHT){
        return this.rotationLR(node);
      }
    }

    if(balanceFactor === BalanceFactorEnum.UNBALANCED_RiGHT){
      const balanceFactorRight = this.getBalanceFactor(<TreeNode<T>>node.right)
      if(balanceFactorRight === BalanceFactorEnum.SLIGHTLY_UNBALANCED_RiGHT || balanceFactorRight === BalanceFactorEnum.BALANCED){
        return this.rotationRR(node);
      }
      if (balanceFactorRight === BalanceFactorEnum.SLIGHTLY_UNBALANCED_LEFT){
        return this.rotationRL(node);
      }
    }

    return node;
  }
}
